#include<iostream>
#include<string>
#include<vector>
using namespace std;
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};
class Solution {
public:
	vector<TreeNode*> v;
	void _Convert(TreeNode* pRootOfTree)
	{
		if (pRootOfTree == nullptr) return;
		_Convert(pRootOfTree->left);
		v.push_back(pRootOfTree);
		_Convert(pRootOfTree->right);
	}
	TreeNode* Convert(TreeNode* pRootOfTree) {

		_Convert(pRootOfTree);
		TreeNode* head = nullptr;
		TreeNode* cur = head;
		for (auto it : v)
		{
			if (head == nullptr)
			{
				head = it;
				cur = head;
			}
			else {
				head->right = it;
				it->left = head;
				head = it;
			}

		}
		return cur;
	}
};
